import collections
import functools


class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        d = collections.defaultdict(set)
        du = {i: 0 for i in range(n)}
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] % nums[j] == 0:
                    d[j].add(i)
                    du[i] += 1
                if nums[j] % nums[i] == 0:
                    d[i].add(j)
                    du[j] += 1
        now_set = set()

        @functools.cache
        def search(id):
            out = [nums[id]]
            if not d[id]:
                return out
            else:
                max_out = []
                for next_id in d[id]:
                    temp_out = search(next_id)
                    if len(temp_out) > len(max_out):
                        max_out = temp_out
                return out + max_out

        for key in du:
            if du[key] == 0:
                now_set.add(key)
        max_out = [nums[0]]
        for key in now_set:
            temp_out = search(key)
            if len(temp_out) > len(max_out):
                max_out = temp_out

        return max_out


data = Solution()
nums = [1, 2, 3, 6, 8, 12]
print(data.largestDivisibleSubset(nums))
